package personal_exercise;

import model.ListNode;
import model.Node;
import model.TreeNode;

import java.util.*;

public class Demo8 {


    // 665. 非递减数列
    public boolean checkPossibility(int[] nums) {
        // 求最长非递减子序列
        int n = nums.length;
        if (n == 1) return true;

        int count = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (count > 0) return false;
                // 先让 nums[i] 变小，判断大小关系是否成立；否则让 nums[i + 1] 变大
                int tmp = nums[i];
                nums[i] = nums[i + 1];
                if (i - 1 >= 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i] = nums[i + 1] = tmp;
                }
                count++;
            }
        }
        return true;
    }



    // 826. 安排工作以达到最大收益
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        Integer[] indexs = new Integer[n];
        for (int i = 0; i < n; i++) indexs[i] = i;
        // 1. 按工作难度排序,按下标排序
        Arrays.sort(indexs, (a, b) -> difficulty[a] - difficulty[b]);

        // 2. dp[i]: 以下标 i 为结尾的所有工作中收益最大的工作
        int[] dp = new int[n];
        dp[0] = profit[indexs[0]];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(profit[indexs[i]], dp[i - 1]);
        }

        // 3. 二分查找每个工人工作的最大承受能力
        int res = 0, m = worker.length;
        for (int i = 0; i < m; i++) {
            int power = worker[i];
            int left = 0, right = n - 1, mid;
            // 寻找工作能力范围内的最右端点
            while (left < right) {
                mid = left + (right - left + 1) / 2;
                if (difficulty[indexs[mid]] > power) right = mid - 1;
                else left = mid;
            }
            // 判断工人能否完成该工作
            if (power >= difficulty[indexs[left]]) res += dp[left];
        }
        return res;
    }




    // 1002. 查找共用字符
    public List<String> commonChars(String[] words) {
        int[] common = new int[26];
        for(char ch : words[0].toCharArray()) {
            common[ch - 'a']++;
        }

        int n = words.length;
        for (int i = 1; i < n; i++) {
            int[] tmp = new int[26];
            for(char ch : words[i].toCharArray()) {
                if (common[ch - 'a'] > tmp[ch - 'a']) tmp[ch - 'a']++;
            }
            common = tmp;
        }

        List<String> res = new ArrayList<>();
        for (char ch = 'a'; ch <= 'z'; ch++) {
            while (common[ch - 'a']-- > 0) {
                res.add("" + ch);
            }
        }
        return res;
    }


    // 面试题 02.06. 回文链表
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转 slow  ~ fast 之间的链表
        ListNode newHead = null, tmp = slow;
        if (fast != null) fast = fast.next;
        while (slow != fast) {
            ListNode next = slow.next;
            slow.next = newHead;
            newHead = slow;
            slow = next;
        }
        prev.next = tmp;
        tmp.next = prev;

        while (head != newHead) {
            if (head.val != newHead.val) return false;
            if (head.next == newHead) break;
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }



    // 24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = new ListNode();
        ListNode tail = newHead, cur = head;

        while (cur != null && cur.next != null) {
            ListNode next = cur.next.next;
            tail.next = cur.next;
            cur.next.next = cur;
            cur.next = null;
            tail = cur;
            cur = next;
        }
        tail.next = cur;
        return newHead.next;
    }



    // LCR 068. 搜索插入位置
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return nums[left] < target ? left + 1 : left;
    }



    // 922. 按奇偶排序数组 II
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int odd = 1, even = 0;
        while (odd < n && even < n) {
            while (odd < n && nums[odd] % 2 == 1) odd += 2;
            while (even < n && nums[even] % 2 == 0) even += 2;
            if (odd < n && even < n) {
                int tmp = nums[odd];
                nums[odd] = nums[even];
                nums[even] = tmp;
            }
            odd += 2;
            even += 2;
        }
        return nums;
    }



    // 844. 比较含退格的字符串
    public boolean backspaceCompare(String s, String t) {
        return changeStr(s).equals(changeStr(t));
    }

    public String changeStr(String s) {
        StringBuilder ret = new StringBuilder();
        for(char ch : s.toCharArray()) {
            if(ch != '#') {
                ret.append(ch);
            } else {
                if(ret.length() > 0) ret.deleteCharAt(ret.length() - 1);
            }
        }
        return ret.toString();
    }


    // 925. 长按键入
    public boolean isLongPressedName(String name, String typed) {
        int n = name.length(), m = typed.length();
        if (n > m) return false;

        int i = 0, j = 0;
        while (i < n && j < m) {
            if (name.charAt(i) == typed.charAt(j)) {
                char ch = name.charAt(i);
                int index1 = i, index2 = j;
                while (i < n && name.charAt(i) == ch) i++;
                while (j < m && typed.charAt(j) == ch) j++;
                if (i - index1 > j - index2) return false;
            } else {
                return false;
            }
        }
        return i == n && (j == m || typed.charAt(j) == name.charAt(n - 1));
    }



    // 205. 同构字符串
    public boolean isIsomorphic(String s, String t) {
        //
        char[] hash = new char[128];
        boolean[] flag = new boolean[128];
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if (hash[c1] != 0 && hash[c1] != c2) return false;
            if (hash[c1] == 0 && flag[c2]) return false;
            hash[c1] = c2;
            flag[c2] = true;
        }
        return true;
    }



    // 141. 环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        return slow == fast;
    }


    // 143. 重排链表
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        prev.next = null;

        // 头插法反转链表
        ListNode tmpHead = null;
        while (slow != fast) {
            ListNode next = slow.next;
            slow.next = tmpHead;
            tmpHead = slow;
            slow = next;
        }

        ListNode res = new ListNode();
        ListNode tail = res;
        while (head != null && tmpHead != null) {
            tail.next = head;
            head = head.next;
            tail.next.next = tmpHead;
            tail = tmpHead;
            tmpHead = tmpHead.next;
        }
        tail.next = head;
        head = res.next;
    }



    // 116. 填充每个节点的下一个右侧节点指针
    public Node connect(Node root) {
        if(root == null) return root;
        Node head = root;
        while (head != null) {
            Node tmpHead = new Node();
            Node tail = tmpHead;
            while (head != null) {
                if (head.left != null) {
                    tail.next = head.left;
                    tail = tail.next;
                }
                if (head.right != null) {
                    tail.next = head.right;
                    tail = tail.next;
                }
                head = head.next;
            }
            head = tmpHead.next;
        }
        return root;
    }



    // 100. 相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }



    // 1382. 将二叉搜索树变平衡
    List<Integer> list;
    public TreeNode balanceBST(TreeNode root) {
        // 1. 中序遍历得到所有结点的值（从小到大）
        list = new ArrayList<>();
        inorder(root);
        // 2. 分治法——根左右构造平衡二叉搜索树
        return buildTree(list, 0, list.size() - 1);
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
    private TreeNode buildTree(List<Integer> list, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = buildTree(list, left, mid - 1);
        root.right = buildTree(list, mid + 1, right);
        return root;
    }



    // LCR 049. 求根节点到叶节点数字之和
    private static int res = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    private void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            res += sum;
            return;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }



    // LCR 108. 单词接龙
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 保存字典 wordList 中的所有单词
        Set<String> hash = new HashSet<>();
        hash.addAll(wordList);
        if (!hash.contains(endWord)) return 0;
        // 保存转换过程中出现的单词
        Set<String> convert = new HashSet<>();
        convert.add(beginWord);

        Queue<StringBuilder> q = new LinkedList<>();
        q.offer(new StringBuilder(beginWord));

        int res = 1;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                StringBuilder cur = q.poll();
                for (int i = 0, len = cur.length(); i < len; i++) {
                    for (int j = 0; j < 26; j++) {
                        if (cur.charAt(i) - 'a' == j) continue;
                        char ch = cur.charAt(i);
                        cur.setCharAt(i, (char)('a' + j));
                        String tmp = cur.toString();
                        if (hash.contains(tmp) && !convert.contains(tmp)) {
                            if (tmp.equals(endWord)) return res + 1;
                            q.offer(new StringBuilder(tmp));
                            convert.add(tmp);
                        }
                        cur.setCharAt(i, ch);
                    }
                }
            }
            res++;
        }
        return 0;
    }



    // 841. 钥匙和房间
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] vis = new boolean[rooms.size()];
        dfs(rooms, vis, 0);
        for (boolean b : vis) {
            if (!b) return false;
        }
        return true;
    }
    private void dfs(List<List<Integer>> rooms, boolean[] vis, int pos) {
        vis[pos] = true;
        for (Integer x : rooms.get(pos)) {
            if (!vis[x]) dfs(rooms, vis, x);
        }
    }


    // 1221. 分割平衡字符串
    public int balancedStringSplit(String s) {
        int res = 0;
        int R = 0, L  = 0;
        for (char ch : s.toCharArray()) {
            if (ch == 'R') R++;
            else L++;
            if (R == L) {
                res++;
                R = L = 0;
            }
        }
        return res;
    }


    // 649. Dota2 参议院
    public String predictPartyVictory(String senateStr) {
        char[] senate = senateStr.toCharArray();
        int n = senate.length;
        // R 为 true 表示本轮投票还有 R；D 为 true 同理
        boolean R = true, D = true;
        // flag > 0 表示有 R 在 D 前面，R 可以禁止 D； flag < 0 表示有 D 在 R 前面, D 可以禁止 R
        int flag = 0;

        while (R && D) {
            R = D = false;
            for (int i = 0; i < n; i++) {
                if (senate[i] == 'R') {
                    if (flag < 0) {
                        senate[i] = 0;
                    }
                    else {
                        R = true;
                    }
                    flag++;
                }
                if (senate[i] == 'D') {
                    if (flag > 0) {
                        senate[i] = 0;
                    }
                    else {
                        D = true;
                    }
                    flag--;
                }
            }
        }
        return R ? "Radiant" : "Dire";
    }



    // 684. 冗余连接
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        // 1. 初始化并查集
        int[] father = new int[n + 1];
        for (int i = 1; i <= n; i++) father[i] = i;

        for (int i = 0; i < n; i++) {
            int[] edge = edges[i];
            int x = edge[0], y = edge[1];
            // 2. 构建并查集， join(x, y)
            if (isSame(father, x, y)) {
                return edge;
            } else {
                join(father, x, y);
            }
        }
        return new int[2];
    }
    private void join(int[] father, int x, int y) {
        x = find(father, x);
        y = find(father, y);
        if (x == y) return;
        // 两根节点相连
        father[x] = y;
    }
    private int find(int[] father, int x) {
        if (father[x] == x) return x;
        // 路径压缩
        return father[x] = find(father, father[x]);
    }
    private boolean isSame(int[] father, int x, int y) {
        return find(father, x) == find(father, y);
    }



    // 685. 冗余连接 II
    class Solution {
        private int[] father;

        public int[] findRedundantDirectedConnection(int[][] edges) {
            int n = edges.length;
            // 1. 并查集初始化
            father =  new int[n + 1];
            for (int i = 1; i <= n; i++) {
                father[i] = i;
            }
            // 2. 统计各边的入度
            int[] inDegree = new int[n + 1];
            for (int[] e : edges) {
                inDegree[e[1]]++;
            }
            // 3. 若存在入度为 2 的节点，则相连的边加入集合
            List<Integer> twoDegree = new ArrayList<>();
            for (int i = n - 1; i >= 0; i--) {
                int node = edges[i][1];
                if (inDegree[node] == 2) twoDegree.add(i);
            }
            // 若集合不为空，则删除其中一条边
            if (!twoDegree.isEmpty()) {
                if (isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {
                    return edges[twoDegree.get(0)];
                }
                return edges[twoDegree.get(1)];
            }

            // 5. 所有节点的入度都为 1，删除构成环的边
            for (int i = 0; i < n; i++) {
                int[] e = edges[i];
                int x = e[0], y = e[1];
                if (isSame(x, y)) return e;
                join(x, y);
            }
            return new int[0];
        }
        private int find(int x) {
            if (father[x] == x) return x;
            return father[x] = find(father[x]);
        }
        private void join(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;
            father[x] = y;
        }
        private boolean isSame(int x, int y) {
            return find(x) == find(y);
        }
        private boolean isTreeAfterRemoveEdge(int[][] edges, int index) {
            for (int i = 0; i < edges.length; i++) {
                if (i == index) continue;
                int[] e = edges[i];
                int x = e[0], y = e[1];
                if (isSame(x, y)) return false;
                join(x, y);
            }
            return true;
        }
    }



    // 657. 机器人能否返回原点
    public boolean judgeCircle(String moves) {
        int rows = 0, cols = 0;
        for (char ch : moves.toCharArray()) {
            if (ch == 'L') cols--;
            if (ch == 'R') cols++;
            if (ch == 'U') rows--;
            if (ch == 'D') rows++;
        }
        return rows == 0 && cols == 0;
    }



    // 463. 岛屿的周长
    private int[] dx = {0,0,1,-1};
    private int[] dy = {1,-1,0,0};
    public int islandPerimeter(int[][] grid) {
        int res = 0;
        int n = grid.length, m = grid[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int x = i + dx[k], y = j + dy[k];
                        if (x < 0 || x == n || y < 0 || y == m || grid[x][y] == 0) {
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }




    // 1356. 根据数字二进制下 1 的数目排序
    public int[] sortByBits(int[] arr) {
        Arrays.sort(arr);
        List<Integer>[] countList = new List[32];
        Arrays.setAll(countList, i -> new ArrayList<>());
        for (int x : arr) {
            int tmp = x, count = 0;
            while (tmp > 0) {
                count++;
                tmp &= (tmp - 1);
            }
            countList[count].add(x);
        }

        int n = arr.length, k = 0;
        int[] res = new int[n];
        for (int i = 0; i < 32; i++) {
            for (int x : countList[i]) {
                res[k++] = x;
            }
        }
        return res;
    }
}
